1. Field of the Invention
The present invention relates to an improved technique for processing information using a computer network, and more particularly to an improved technique for distributed processing with regard to constraint satisfaction problem and an improvement in technology for readily realizing flexible bonding of a plurality of the existing systems.
2. Description of the Related Art
Recently, a practical approach using the framework of a constraint satisfaction problem (CSP) has been made to various problems including production scheduling problems and facilities and parts layout problems. The constraint satisfaction problem refers to a problem of finding a combination of values satisfying a constraint for a plurality of variables.
In a constraint satisfaction problem, individual elements such as facilities or parts constituting an actual problem are represented by variables. In this case, there are many constraints that may include one requiring that the facilities and the parts be placed at least a predetermined distance apart between each two of them. These constraints are represented as constraints among variables. An actual thing, such as which one of several alternatives is to used or where in a plane or on a time-axis each element is to be placed, is represented by a specific value of each variable. After that, finding the values of the individual variables that satisfy the above-described constraint gives a solution of the problem.
That is, to fund a solution is to find a combination of variable values that satisfy the constraint. A combination of such variable values represents, for instance, a working schedule or a semiconductor device layout. A part of a solution, for example, a combination of some of the variables, is called a partial solution. The processing of such a constraint satisfaction problem is based on the branch search that performs a search, for example, when there are several branches that are capable of acquiring several alternative variable values, with regard to what kind of alternatives exist as the next branches according to which one is selected from the current several branches.
Knowledge about problem solving, such as a processing procedure for solving a constraint satisfaction problem, is called problem solving knowledge. Knowledge about the elements, or variables, of a target, such as a schedule or a layout, to be solved as a constraint satisfaction problem and about a constraint among the elements or variables is called target knowledge.
One known solving method for this constraint satisfaction problem is a method in which a single problem solver provides knowledge about the problem and, at the same time, dissolves all the constraints. 'Ib “dissolve” a constraint is to assign specific values not conflicting with the constraint. FIG. 22 is a diagram showing the concept of a single problem solver which has both problem solving knowledge and target knowledge. The problem solver calls a method corresponding to individual target knowledge for problem solving.
However, for a large constraint satisfaction problem such as an actual scheduling problem, a target for which problem solving is performed is physically distributed and, in most cases, the decision making actions at several levels are performed concurrently. In addition, assigning all tasks to the single problem solver requires the unified management of a large amount of data and results in the disclosure of information associated with the local aspect of the problem at one particular point, thus making it difficult to ensure security.
In particular, it is difficult to apply the single, centralized system described above to an actual large problem. The constraint satisfaction problem is, for example, a power cut plan for work of electric power system facilities. The power cut plan for work of electric power system facilities sets up dates on which power transmission will be temporarily suspended to maintain, replace, or add various types of facilities (bus bar, power transmission line, power generator, transformer, etc.).
Most conventional systems for supporting the power cut plan for work of electric power system facilities collect the schedules of all stations in one location (Reference: “Development of Support System of Power Cut Plan for World” by Akitomo Otubo, Toshio Takahasi, Datashi Saito, Kazue Simada, Masaya Ono, Hirotaka Nakano, Yosiaki Osako, pp. 138–139, 1997 Power System Convention, 1997). However, the system according to the prior art such as described above must perform a huge amount of centralized calculation and therefore requires a long processing time because the scale is very large. In addition, when the result of centralized calculation is not accepted by stations, the centralized calculation must be repeated. This sometimes causes a communication bottleneck.
Another problem is that the centralization of processing or communication loads decreases the applicability to the dynamic environment in the real world. For this reason, a method for modeling an actual large constraint satisfaction problem and for solving the problem efficiently with a plurality of solvers in the distributed coordination mode is now being studied.
This problem solving method, which works in the distributed coordination mode through a plurality of problem solvers, allows individual stations in the electric power system to work together to solve constraints coordinatable locally among themselves, except when the constraints require system-wide information as in a current calculation. This method gives us many advantages; that is, it reduces the centralized calculation load, reduces the coordination time, and results in fewer modification requests from the schedule made by each station.
Recently, many actual problems are modeled as large constraint satisfaction problems. And, as the means for solving such modeled problems efficiently, more emphasis is placed now on the constraint satisfaction problem solving method which works in the distributed coordination mode described above.
The method for satisfying constraints in the distributed coordination mode is called a distributed constraint satisfaction or a distributed constraint satisfaction problem. The method sometimes uses a plurality of equal agents (problem solvers). Standard algorithms used for this method include the synchronous backtrack algorithm and the asynchronous backtrack algorithm (Reference: “Tutorial Distributed Search and Its Surroundings” by Makoto Yokoo, Computer Software Vol. 12, No. 1, pp. 31–86, January 1995/“New Development of CSP: Distributed/Dynamic/Incomplete CSP” by Makoto Tokoo, Katsutosi Hirayama, Artificial Intelligence, Vol. 12, No. 3., pp. 381–389, May. 1997).
The synchronous backtrack algorithm executes the backtrack type search algorithm using a plurality of agents. In this algorithm, the order in which agents determine their variables is fixed. More specifically, the first agent temporarily determines the values of its own variables and sends the values (partial solution) to the next agent. The next agent determines the values of its own variables so that the values satisfy both the partial solution and the constraint and adds the values to the partial solution; it then sends the resulting partial solution to the next agent.
When some agent tries to determine the values of its own variables but finds that there is no value satisfying the partial solution and the constraint, the agent sends a value-change request (backtrack) message to the previous agent.
In this synchronous backtrack algorithm, agents send the partial solution serially, allowing the knowledge owned by individual agents to be integrated and thereby giving a solution satisfying the constraints.
Sycara and his group proposed the back jumping algorithm developed by improving the search efficiency of the above-described backtrack algorithm. They are studying the application of that algorithm to the scheduling problem. (Reference: Sycara, K. P, Sadeh, N. and Fox, M. S., “Distributed constrained heuristics search”, IEEE Transactions on Systems, Man And Cybernetics, Vol. 21, No.6, pp. 1446–1461, 1991. Sycara, K. P, Roth, S. F., Sadeh, N. and Fox, M. S., “Resource Allocation in Distributed Factory Scheduling”, IEEE Expert, Vol. 6, No.1, pp. 29–40, 1991).
Unlike the backtrack algorithm described above, the asynchronous backtrack algorithm allows the agents to determine their own values asynchronously and concurrently based on the local information. And, the agents exchange the new constraint (nognod) with each other to find a combination of variable values satisfying the system-wide constraints.
The distributed constraint satisfaction technology like this include CORBA (Common Object Request Broker Architecture), an ORB (Object Request Broker) proposed by OMG (Object Management Group). The ORB is a mechanism responsible for execution, communication, and management of functionally-divided applications, each composed of objects, in a distributed system. This architecture not only provides the applications with the basic operation of the objects but also allows the applications to use sophisticated common and generic functions, such as printing and data exchange. It also provides business applications with the services common to all applications as well as the services specific to each application.
FIG. 23 is a diagram showing the concept of the architecture like CORBA described above. As shown in the figure, each object has both problem solving knowledge and target knowledge. lb perform processing necessary for the target knowledge owned by an object, the object sends a message to some other object to use the method owned by that object.
Another distributed constraint satisfaction architecture is disclosed in Japanese Patent Laid-Open No. Hei 7-6157 and Japanese Patent Laid-Open No. Hei 9-91431. In this architecture, the agents resident in some nodes (called stationary agents) are used as schedulers each of which performs direct negotiation with other schedulers (hereinafter called “direct negotiation model”).
FIG. 24 is a diagram showing how a plurality of stationary agents SA perform direct negotiation with each other. Note that, in the direct negotiation model, agents, not the objects, are used and that they are autonomous. Therefore, as shown in the conceptual diagram in FIG. 25, each agent autonomously decides which method to use according to the condition under which the agent processes its own target knowledge.
Another method of sharing knowledge is also known, such as a facilitator model implemented through DARPA knowledge sharing activity (The DARPA Knowledge Sharing Effort). In this model, a plurality of agents use the coordination facilitator to exchange knowledge via the common language for exchanging common knowledge (“Knowledge Sharing and Reuse through Coordination Architecture” by Toyoaki Nishida, Artificial Intelligence Society Magazine, Vol. 9, No. 1, January 1994, pp. 23–28). That is, in the facilitator model, the agents exchange knowledge via one facilitator.
However, the prior art of distributed constraint satisfaction described above has the following problems. First, for an ORB such as CORBA and the direct negotiation model described above, the communication functions such as the highly-sophisticated message routing function or communication protocol must be included in advance. This makes it difficult to develop a distributed scheduling system and to utilize the existing scheduling system.
In addition, including these communication functions into individual schedulers results in the already-included protocol being always used as the scheduler coordination protocol, making it difficult to add or change the protocol. Thus, it is difficult to efficiently implement or use the constraint satisfaction algorithm, best suited for the constraint type, for use as the coordination protocol. The coordination protocol, a protocol defining a sequence of information exchange actions among a plurality of subjects to achieve an object, may be represented, in general, as a state transition diagram.
In addition, including complex processing, such as scheduler communication or branch search, into the individual schedulers constituting the direct negotiation model results in the frequent data exchange among schedulers especially when the variables of the schedulers must be coordinated step by step. This increases both the processing load of the individual schedulers and the communication amount over the network connecting the schedulers.
When a branch search fails due to a network error and the search of a part is terminated abnormally in the ORB or the direct negotiation model described above, the whole processing is influenced.
In the facilitator model described above, communication processing centralization in one facilitator causes a system bottleneck. In addition, the facilitator performs only simple message routing but does not virtually perform coordination processing. That is, the facilitator is not responsible for the progress of the whole processing, nor does it tell the individual schedulers what to do next.
Another problem with the constraint satisfaction method in the above-described distributed coordination mode is that heuristics is not reflected on the solution. Heuristics, also called an exploratory method, is thought of as a rule-of-thumb equation in which solutions are discovered by evaluation of the progress made toward the final result.
It is pointed out that, in general, solution search efficiency depends largely on the heuristics factors such as a strategy for the decision of individual agent variables or the variable decision priority order among agents (Reference: “Constraint Based Search and Its Application” by Kazuo Miyashita, Artificial Intelligence Magazine, Vol. 12, No. 3, pp. 374–380, May 1997). For a constraint satisfaction problem having a plurality of solutions, heuristics has a strong impact on the quality of the final solution.
Typical heuristics includes the ability to switch the strategy or the priority described above depending upon the situation. However, since the strategy and the priority are determined by the system configuration according to the conventional algorithm for distributed constraint satisfaction, heuristics cannot be reflected well on the processing and, as a result, it is difficult to increase the quality of search efficiency and quality.
Consider the power cut plan for work of electric power system facilities described above as an example. The coordination among stations is not fixed but varies according to the period of the year (busy season and off-season), the relation among stations, or the processing power of maintenance companies. And, the selection and the weighting of objects depend dynamically on such changeable factors as the priority of schedule coordination, min;mi˜.˜tion of movement during the work period, averaging of work load, and reduction in the number of suspensions.
Thus, coordination should be made more flexible depending upon the situation by using the coordination method or strategy In addition, it is expected that Japanese electric power companies will have power generation departments and power transmission departments in the near future like European and American power companies and that medium and small-sized electric generation companies will enter the electric power industry. If such is the case, it is desirable that a flexible coordination method be used, instead of the conventional fixed coordination method, to satisfy the need from the requesting stations and requesting departments directly and easily.
However, the method according to the prior art uses a fixed strategy and priority. Even if the strategy may be changed, the whole processing must be reexecuted each time the strategy is changed. Re-executing the whole processing for each strategy change requires a long time; in addition, it does not satisfy the need to find a solution more speedily.
Conventionally, even when there are a plurality of agents with equal priority, the method according to the prior art selects one of the agents sequentially. This method does not always give a solution satisfying individual agents and, therefore, there has been a need to increase the quality of a solution.
On the other hand, as computer networks have become popular rapidly, interconnection among applications over the network becomes more important.
In particular, in conjunction with the setup of the network infrastructure and the trend toward the openness of application software, the need arises to interconnect applications via the network. (Reference: “Software agents” by Genesereth, M. R. and Ketchpel, S. P, Special Issue on Intelligent Agents, Communications of the ACM, Vol. 37, No. 7, pp. 48–53, July. 1994/“Mobile Agent Technology Implementing Network Society” by Shiniti Motoida, Takashi Moriyasu, Takahiro Kawamura, Toshiba review, Vol. 53, No. 8, pp. 2–6, August 1998).
More specifically, it is desirable that the existing dedicated program, called the legacy system, and existing databases be used as much as possible and that, by working them together, efficient distributed systems be built and managed.
Representative applications include an experiment, called CALS (Commerce At Light Speed), which digitizes information relating to the whole life cycle of a product, EC (Electronic Commerce) such as online shopping, and inter enterprise EC aiming at the electronic commerce among enterprises. lb implement those applications, interconnection among applications over networks is a key to success.
Nowadays, a variety of technologies and standards are proposed to implement inter-system data exchange over networks. Some of the examples include SGML which is a document processing description system, XML which is a network version of SGML, and STEP which is used for representation and exchange of product technology data.
However, consistent operation of a distributed system requires knowledge sharing based on data exchange as well as the coordination among constituent elements that composes the distributed system. Lack of such a coordination function impairs the merit of the distributed system. However, in the conventional environment to develop such distributed system has never supported the coordination function sufficiently.
Recently, efforts have been made to develop a distributed object system using distributed system constituent elements as objects and a multi-agent system composed of a plurality of coordinating agents. However, most of development support tools for use on these systems have communication functions among constituent elements but not coordination functions among them. Therefore, a framework providing not only communication functions but also coordination functions is required. This framework is a partially completed software product used to create specific parts for use in building an actual distributed system.
That is, recently, the distributed architecture is shifting from the conventional client-server model (FIG. 26) to the distributed object model (FIG. 27) which may be built more flexibly. This type of distributed object model generally requires that the connected systems understand each other and that modeling and interface specifications be defined rigidly. For example, knowledge about the object (IDL interface and so on) of a remote partner must be known in advance. In addition, because the logic of coordination among a plurality of objects is not supported in the conventional object-oriented programming system, the object designer must include the logic into individual objects.
On the other hand, for the multi-agent model which is now under study, the constituent elements of a distributed system are regarded as agents. Several models are proposed for executing coordination among a plurality of agents.
Those models include KQML facilitators (Reference: “Actors: A model of Concurrent Computation in Distributed Systems” by Agha, G., The MIT Press, 1986/“An Overview of KQML: A knowledge Query and Manipulation Language” by Finin, T. and Wiederhold, G., Department of Computer Science, Stanford University, 1993./“The DARPA Knowledge Sharing Effort: Progress report” by ¥bibitem{DARPA} Paaatil, P. S., Fikes, R. E., Patel-Schneider, R. E., Macay, D., Finin, T., Gruber, T. R. and Neches, R., Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning, 1992.) and a model called a federation model.
However, these models place emphasis on speedy routing of each message in a system where connected agents interact with each other based on the exchange of KQML messages. This means that the models do not support the higher-level coordination function deciding how to solve the problem based on the messages received by a plurality of agent or issued from the user.
Agent development tools for the higher-level coordination function include COOL (Reference: “Cool: A language for describing coordination in multi agent systems” by Barbuceanu, M. and Fox, M. S., Proceedings of the First International Conference on Multi-Agent Systems, 1995.) and JAFMAS (Reference: “JAFMAS: A JAVA-based Agent Framework for Multiagent Systems Development and Implementation” by Chauhan, D., phD thesis, ECECS Department, University of Cincinnati, 1997).
These tools propose the general methodology for developing a multi-agent system based on Speech-Act (Reference: “How to do Things With Words” by Austin, J. L.(ed), Oxford University Press, 1962). At the same time, the tools support an interaction protocol (hereinafter called IP) for explicitly representing inter-dependency among KQML messages. This IP, primarily composed of the communication element and the coordination element, is a procedure allowing constituent elements, such as applications, to communicate with each other and to coordinate the constituent elements to solve a given problem.
However, creating the IP with the use of these tools is very complex. This is because each agent must have its own dedicated IP and that the IPs of all agents must be compatible. Therefore, when the user wants to add or modify some part of a problem solving procedure at initial time or during a production run, the complex interaction flow among agents must be broken down into the IP of each individual agents compatibly and repeatedly.
In particular, this task is impractical when there are many related agents or when the problem solving procedure is very complex. At the same tune, verifying whether or not the IPs of the agents are compatible becomes more difficult.
That is, the prior art attempted to achieve two objects at the same time: to process the difference in the interface formats which vary each constituent element just as dialects vary from district to district and to coordinate the interaction among individual constituent elements. This makes it difficult to develop the IP efficiently.